package leetcode.set_map;

/**
 * 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
 * <p>
 * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
 * <p>
 * 注意:
 * 假设字符串的长度不会超过 1010。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * "abccccdd"
 * <p>
 * 输出:
 * 7
 * <p>
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 * 分析:进行统计每一个单词出现的次数, 使用2数组进行统计, 先只进行偶数次的使用,假设每一个单词只进行偶数次的使用 则此时回文串的长度为: res+=x-(x&1)
 * 时间复杂度 On
 * 空间复杂度 O 1
 */
public class Solution409 {

    public static int longestPalindrome(String s) {
        int[] freq = new int[128];

        //统计字符串中每一个字母出现的次数
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freq[c] += 1;
        }
        int res = 0;
        for (int i = 0; i < freq.length; i++) {
            int x = freq[i];
            //每一个字符被用偶数次  01 & 100 = 100  101 & 001 = 001 =1
            res += x - (x & 1);
        }
        //进行比较是否存在字母只出现过一次,如果有可以放中间,
        return res < s.length() ? res + 1 : res;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("zeusnilemacaronimaisanitratetartinasiaminoracamelinsuez"));
    }
}
